// 11.3 关联容器操作
/**
 * 除了表9.2（第295页）中列出的类型，关联容器还定义了表11.3中列出的类型。这些类型表示容器关键字和值的类型。[插图]
 * 1. key_type     此容器类型的关键字类型
 * 2. mapped_type  每个关键字关联的类型，即值的类型，只适用于map
 * 3. value_type   对于set，与key_type相同；对于map，为pair<const key_type,mapped_type>
 * 与顺序容器一样（参见9.2.2节，第297页），我们使用作用域运算符来提取一个类型的成员——例如，map<string，int>：：key_type。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
using namespace std;

int main()
{
    // 11.3.1 关联容器迭代器
    // 当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用。
    map<string, size_t> word_count = {{"abc", 1}, {"xyz", 2}, {"efg", 3}};
    auto map_it = word_count.begin(); // 获得指向word_count中一个元素的迭代器
    // *map_it是指向一个pair<const string, size_t>对象的引用
    cout << map_it->first << " ";  // 打印此元素的关键字
    cout << map_it->second << " "; // 打印此元素的值
    // map_it->first = "new key"; // 错误，关键字是constd的
    cout << ++map_it->second << endl; // 正确，我们可以通过迭代器改变元素
    // 必须记住，一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字成员的值。

    // set的迭代器是const的
    // 可以用一个set迭代器来读取元素的值，但不能修改：[插图]
    set<int> iset = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    set<int>::iterator set_it = iset.begin();
    if (set_it != iset.end())
    {
        // *set_it = 42; // 错误：set中的关键字是只读的
        cout << *set_it << endl; // 正确：可以读关键字
    }

    // 遍历关联容器
    map<string, size_t> word_count1 = {{"abc", 1}, {"xyz", 2}, {"efg", 3}};
    auto map_it1 = word_count1.begin(); // 获得指向word_count中一个元素的迭代器
    while (map_it1 != word_count1.end())
    {
        cout << map_it1->first << " " << map_it1->second << endl; // 解引用迭代器，打印关键字-值对
        ++map_it1;                                                // 递增迭代器，移动到下一个元素
    }
    // 本程序的输出是按字典序排列的。当使用一个迭代器遍历一个map、multimap、set或multiset时，迭代器按关键字升序遍历元素。

    // 关联容器和算法
    // 我们通常不对关联容器使用泛型算法（参见第10章）。关联容器可用于只读取元素的算法。
    // 由于关联容器中的元素不能通过它们的关键字进行（快速）查找，因此对其使用泛型搜索算法几乎总是个坏主意。
    // 使用关联容器定义的专用的find成员会比调用泛型find快得多。

    return 0;
}